순차 탐색(Sequential Search)

특정원소를 찾기 위해 원소를 순차적으로 하나씩 탐색하는 방법

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define LENGTH 100

char **array;

int founded;

int main(void){

int n;

char *word;

word=malloc(sizeof(char *100));

scanf("%d %s", &n, word);

array=(char**)malloc(sizeof(char*)*n);

for(int i=0;i<n;i++){

array[i]=malloc(sizeof(char)*LENGTH);

scanf("%s", array[i]);

}

for(int i=0;i<n;i++){

if(!strcmp(array[i], word)){

printf("%d번째 원소 입니다.\n", i+1);

founded=1;

}

if(!founded)printf("원소를 찾을 수 없습니다.");

system("pause");

return 0;

}

순차 탐색은 데이터 정렬 유무에 상관 없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 점에서 O(N)의 시간 복잡도를 가진다.

이진 탐색(Binary Search)

배열 내부 데이터가 이미 정렬 되어 있는 상황에서 사용 가능한 알고리즘. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<stdlib.h>

#define MAX_SIZE 100000

int a[MAX_SIZE];

int founded=0;

int search(int start, int end, int target){

if(start>end)return -9999;

int mid=(strat+end)/2;

if(a[mid]==target)return mid;

else if(a[mid]>target)return search(start,mid-1, target);

else return search(mid+1, end, target);

}

// 단 데이터는 오름차순으로 입력되어야 함

int main(Void){

int n, target;

scaf("%d %d", &n, &target);

for(int i=0;i<n;i+)scanf("%d",&a[i]);

int result=search(0, n-1, target);

if(result!=-9999)printf("%d번째 원소입니다.\n",result+1);

else printf("원소를 찾을 수 없습니다.\n");

system("pause");

return 0;

}

이진탐색은 한 번 확인할 때마다 보아야 하는 원소의 개수가 절반씩 줄어든다는 점에서 O(logN)의 시간 복잡도를 가진다

Sequential Search & Binary Search